\documentclass[12pt,a4paper]{article}
\usepackage{amssymb, amsmath, euscript, multicol}
\usepackage[english,russian]{babel}
\usepackage{amssymb, euscript}
\usepackage[utf8]{inputenc}
%\input hyphen.tex

\pagestyle{empty}
%\topmargin=-2.5cm
%\headheight=0cm
%\headsep=0cm
%\oddsidemargin=-1.8cm
%\textwidth=29cm
\textheight=20cm
\topmargin=-1.5cm
\headheight=0cm
\headsep=0cm
\oddsidemargin=-1.5cm
\textwidth=19cm
\textheight=28cm



\begin{document}



\begin{center}
{\bf Летние сборы 2001.
Сборная команда.
Олимпиада \No 1.}
\end{center}

\textbf{1}.
Известно, что $f(x + y + xy) = f(x) + f(y) + f(xy)$.
Докажите, что $f(x + y) = f(x) + f(y)$.

\textbf{2}.
Внутри окружности $S$ расположено $2n$ окружностей $S_1$, $S_2$, \dots, $S_{2n}$, которые касаются $S$ в точках $T_1$, $T_2$, \dots, $T_{2n}$ соответственно, причем окружности $S_i$ и $S_{i+1}$ касаются внешним образом ($S_1 = S_{2n + 1}$).
Докажите, что $T_1 T_2 \cdot T_3 T_4 \cdot \dots \cdot T_{2n - 1} T_{2n} = T_2 T_3 \cdot T_4 T_5 \cdot \dots \cdot T_{2n} T_1$.

\textbf{3}.
В группе людей любые два либо знакомы, либо не знакомы, причем у каждого не более $5$ незнакомых.
Докажите, что можно познакомить несколько непересекающихся пар незнакомых людей так, что после этого всех можно будет разбить на $3$ группы, причем люди внутри каждой из групп попарно знакомы.

\begin{center}
{\bf Летние сборы 2001.
Группы А+Б.
Олимпиада \No 1.}
\end{center}

\textbf{1}.
Корни квадратного уравнения $ax^2 - 4bx + 4c = 0$ ($a>0$)
принадлежат отрезку $[2, 3]$. Докажите, что $\displaystyle \frac{{a}}{{a + c}} +
\frac{{b}}{{b + a}} > \frac{{c}}{{c + b}}$.

\textbf{2}.
$ABCDEF$ --- выпуклый шестиугольник, причем $AB=BC$, $CD=DE$, $EF=FA$.
Докажите, что
\[ \frac{BC}{BE} + \frac{DE}{DA} + \frac{FA}{FC} \geqslant \frac{3}{2} .\]

\textbf{3}.
Докажите, что при любых натуральных $t$ и $s$ ($s > t$)
число $\sum\limits_{i = t}^{s} \frac{1}{3i + 1}$ не является целым.

\textbf{4}.
В группе людей любые два либо знакомы, либо не знакомы, причем у каждого не более $5$ незнакомых.
Докажите, что можно познакомить несколько непересекающихся пар незнакомых людей так, что после этого всех можно будет разбить на $3$ группы, причем люди внутри каждой из групп попарно знакомы.


\begin{center}
{\bf Летние сборы 2001.
Сборная команда.
Олимпиада \No 2.}
\end{center}

\textbf{1}.
Клетки прямоугольника $kn \times ln$ ($k$, $l$, $n \geqslant 2$) покрашены в $n$ цветов таким образом, что в любой строчке по $k$ клеток каждого цвета, в любом столбце --- по $l$. При этом нет четырех клеток одного цвета, центры которых образуют прямоугольник со сторонами, параллельными линиям сетки.
Докажите, что $kl$ не превосходит $n(n+1)$.

\textbf{2}.
$ABCD$ --- четырехугольник, вписанный в окружность $S$.
Окружность $S_1$ касается диагонали $AC$ в точке $K$, $BD$ в точке $L$, а также дуги $AD$, не содержащей точек $B$ и $C$.
Окружность $S_2$ касается стороны $AB$ в точке $M$, стороны $CD$ в точке $N$, а также дуги $AD$, не содержащей
точек $B$ и $C$.
Докажите, что точки $M$, $K$, $L$ и $N$ лежат на одной прямой.

\textbf{3}.
Даны натуральные числа $a$ и $b$, большие $1$.
Известно, что для любого натурального $n$ $a^{n}-1$ делится на $b^n-1$.
Докажите, что число $a$ является натуральной степенью числа $b$.

\begin{center}
{\bf Летние сборы 2001.
Группа А.
Олимпиада \No 2.}
\end{center}

\textbf{1}.
Дано множество $S$ из $2n$ элементов. {\it Базисом} $B$ множества $S$ назовем минимальный по числу элементов набор подмножеств множества $S$ такой, что любое подмножество множества $S$ является объединением не более двух подмножеств из $B$.
Пусть в базисе множества $S$ ровно $k$ подмножеств.
Докажите, что $\sqrt{2} \cdot 2^{n} < k \leqslant 2^{n + 1}$.

\textbf{2}.
Дан открытый интервал числовой прямой длины $1/n$ (где $n$ --- натуральное).
Докажите, что на этом интервале лежит не более $(n+1)/2$ несократимых дробей со знаменателями, не превосходящими~$n$.

\textbf{3}.
Докажите, что если в остроугольном треугольнике $ABC$ радиусы описанной и вневписанной, касающейся стороны $BC$, окружностей равны, то прямая, проходящая через центры вписанной и описанной окружностей этого треугольника, проходит через основание высоты, опущенной из вершины $A$ на сторону $BC$.

\textbf{4}.
Клетки прямоугольника $kn \times ln$ ($k$, $l$, $n \geqslant 2$) покрашены в $n$ цветов таким образом, что в любой строчке по $k$ клеток каждого цвета, в любом столбце --- по $l$.
При этом нет четырех клеток одного цвета, центры которых образуют прямоугольник со сторонами, параллельными линиям сетки.
Докажите, что $kl$ не превосходит $n(n+1)$.

\begin{center}
{\bf Летние сборы 2001.
Группа Б.
Олимпиада \No 2.}
\end{center}

\textbf{1}.
Дано множество $S$ из $2n$ элементов. {\it Базисом} $B$ множества $S$ назовем минимальный по числу элементов набор подмножеств множества $S$ такой, что любое подмножество множества $S$ является объединением не более двух подмножеств из $B$.
Пусть в базисе множества $S$ ровно $k$ подмножеств.
Докажите, что $\sqrt{2} \cdot 2^{n} < k \leqslant 2^{n + 1}$.

\textbf{2}.
Дан открытый интервал числовой прямой длины $1/n$ (где $n$ --- натуральное).
Докажите, что на этом интервале лежит не более $(n+1)/2$ несократимых дробей со знаменателями, не превосходящими $n$.

\textbf{3}.
Дано положительное число $a$ и положительные числа $x_1$, $x_2$, \dots, $x_n$, удовлетворяющие соотношению
\[]\frac{1}{a + x_1} + \frac{1}{a + x_2} + \dots + \frac{1}{a + x_n} = \frac{1}{a}.\]
Докажите неравенство $\sqrt[n]{x_1 \cdot x_2 \cdot \dots \cdot x_n} \geqslant (n-1)a$.

\textbf{4}.
Докажите, что если в остроугольном треугольнике $ABC$ радиусы описанной и вневписанной, касающейся стороны $BC$, окружностей равны, то прямая, проходящая через центры вписанной и описанной окружностей этого треугольника, проходит через основание высоты, опущенной из вершины $A$ на сторону $BC$.

\begin{center}
{\bf Летние сборы 2001.
Сборная команда.
Олимпиада \No 3.}
\end{center}

\textbf{1}.
Рассмотрим многочлен $f(x)$ степени $n$, все корни которого вещественны и старший коэффициент равен~$1$.
Докажите, что существует такая абсолютная константа $c$, что для всех таких многочленов выполняется неравенство
\[\max_{0 \leqslant x \leqslant 2} |f(x)| \leqslant c^n \max_{0 \leqslant x \leqslant 1} |f(x)|.\]

\textbf{2}.
Граф называется транзитивным, если все его компоненты связности --- полные подграфы.
Докажите, что граф пересечения отрезков на прямой, в котором никакой отрезок не пересекает $\geqslant n+1$ отрезок, можно разбить на $n$ транзитивных подграфов.
(Граф пересечения отрезков --- это граф, вершины которого --- некоторое конечное множество отрезков прямой, ребрами соединены пересекающиеся отрезки.)

\textbf{3}.
Внутри треугольника $ABC$ выбрана такая точка $M$, что периметры треугольников $AMB$, $BMC$ и $CMA$ равны.
Пусть $r_1$ --- радиус вписанной окружности треугольника $BMC$, а $r_a$ --- радиус вневписанной окружности треугольника $ABC$, касающейся стороны $BC$.
Докажите, что $r_1 + r_a = BC$.

\begin{center}
{\bf Летние сборы 2001.
Группа А.
Олимпиада \No 3.}
\end{center}

\textbf{1}.
Дана перестановка натурального ряда $\tau : \mathbb{N} \to \mathbb{N}$.
Тройка чисел $a_1$, $a_2$, $a_3$ называется монотонной прогрессией, если $2a_2 = a_1 + a_3$ и $\tau(a_1) < \tau(a_2) < \tau(a_3)$.
Докажите, что для любого $\tau$ существует хотя бы одна монотонная прогрессия.
%$\{ \tau_n \}_{n \in \N}$.

\textbf{2}.
Даны положительные числа $a$, $b$ и $c$.
Докажите неравенство \[\frac{a}{b} + \frac{b}{c} + \frac{c}{a} \geqslant \frac{a+b}{b+c} + \frac{b+c}{a+b} + 1 .\]

\textbf{3}.
Внутри треугольника $ABC$ выбрана такая точка $M$, что периметры треугольников $AMB$ и $BMC$ равны.
Пусть $S_1$ --- вписанная окружность треугольника $AMB$, а $S_2$ --- вневписанная окружность треугольника $ABC$, касающейся стороны $BC$.
Докажите, что точка пересечения общих внешних касательных окружностей $S_1$ и $S_2$ лежит на отрезке $CM$.

\textbf{4}.
Многоугольник называется целочисленным, если все его вершины имеют целые координаты.
Докажите, что любой выпуклый целочисленный многоугольник площади $S$ можно заключить в целочисленный параллелограмм площади $4S$.

\begin{center}
{\bf Летние сборы 2001.
Группа Б.
Олимпиада \No 3.}
\end{center}

\textbf{1}.
Дана перестановка натурального ряда $\tau : \mathbb{N} \to \mathbb{N}$.
Тройка чисел $a_1$, $a_2$, $a_3$ называется монотонной прогрессией, если $2a_2 = a_1 + a_3$ и $\tau(a_1) < \tau(a_2) < \tau(a_3)$.
Докажите, что для любого $\tau$ существует хотя бы одна монотонная прогрессия.

\textbf{2}.
Решите в натуральных числах уравнение $a^{5a} = b^b$.

\textbf{3}.
Внутри треугольника $ABC$ выбрана такая точка $M$, что периметры треугольников $AMB$, $BMC$ и $CMA$ равны.
Пусть $O_a$ --- центр вписанной окружности треугольника $BMC$, а $I_a$ --- центр вневписанной окружности треугольника $ABC$, касающейся стороны $BC$.
Аналогично определяются точки $I_b$ и $I_c$.
Точка $O$ --- центр описанной окружности треугольника $I_aI_bI_c$.
Докажите, что прямая $OO_a$ перпендикулярна $BC$.

\textbf{4}.
Какое наименьшее число дорог может быть в стране из $n$ городов, если для любых двух городов $A$ и $B$ найдется отличный от них город $C$, соединенный дорогами и с $A$, и с $B$.

\begin{center}
{\bf Летние сборы 2001.
Сборная команда.
Олимпиада \No 4.}
\end{center}

\textbf{1}.
Сколькими способами из набора чисел $\{1, 2, \dots, 2p \}$ можно выбрать $p$ различных чисел, сумма которых делится на $p$.

\textbf{2}.
Дано $n$ равных параллельно расположенных треугольников площади~$1$.
Их пересечение содержит центр масс каждого из этих треугольников.
Докажите, что площадь их пересечения не меньше чем $1/9$.

\textbf{3}.
Пусть $\smash{\displaystyle S_n = \sum_{k=1}^n \sum_{j=1}^n \frac{1}{\sqrt{j^2 + k^2}}}$.
Докажите неравенство $n \leqslant S_n \leqslant 2\sqrt{2} n$.

\begin{center}
{\bf Летние сборы 2001.
Группа А.
Олимпиада \No 4.}
\end{center}

\textbf{1}.
На окружности отмечено $50$ точек и проведено $50k + 1$ хорд с вершинами в этих точках.
Докажите, что можно так выбрать $k+1$ из этих хорд, что никакие две из них не имеют общих точек.

\textbf{2}.
Решите уравнение $p^x - y^p = 1$, где $x$, $y \in \mathbf{N}$, $p \in \mathbf{P}$.

\textbf{3}.
Четырехугольник $ABCD$ вписан в окружность $S$.
Окружность $S_1$ касается диагонали $BD$ в точке $Q$, диагонали $AC$ в точке $P$ и дуги $BAD$ окружности $S$.
Докажите, что прямая $PQ$ проходит через центр вписанной окружности треугольника $BAD$.

\textbf{4}.
Докажите, что существует такая константа $C$, что для любого натурального $n$ имеет место неравенство $n \leqslant S_n \leqslant Cn$, где $\displaystyle S_n = \sum_{k=1}^n \sum_{j=1}^n \frac{1}{\sqrt{j^2 + k^2}}$.

\begin{center}
{\bf Летние сборы 2001.
Группа Б.
Олимпиада \No 4.}
\end{center}

\textbf{1}.
На окружности отмечено $50$ точек и проведено $50k + 1$ хорд с вершинами в этих точках.
Докажите, что можно так выбрать $k+1$ из этих хорд, что никакие две из них не имеют общих точек.

\textbf{2}.
Докажите, что существует бесконечно много таких составных чисел $n$, что если $a^n - 1 \vdots n$, то $a^n - 1 \vdots n^2$.

\textbf{3}.
Окружности $S_1$ и $S_2$ касаются друг друга внешним образом в точке $C$, а также окружности $S$ внутренним образом в точках $A$ и $B$ соответственно.
Общая касательная к окружностям $S_1$ и $S_2$ в точке $C$ пересекает окружность $S$ в точках $X$ и $Y$.
Прямые $AY$ и $BY$ вторично пересекают $S_1$ и $S_2$ в точках $M$ и $N$ соответственно.
Прямая $AB$ вторично пересекает окружности $S_1$ и $S_2$ в точках $K$ и $L$
соответственно.
Докажите, что прямые $KM$, $LN$ и $XY$ пересекаются в одной точке.

\textbf{4}.
Бесконечная последовательность неотрицательных чисел $\{ a_n \}$ для любого натурального $n$ удовлетворяют условиям $a_n - 2a_{n+1} + a_{n+2} \geqslant 0$ и $a_1 + a_2 + \dots + a_n \leqslant 1$.
Докажите, что для всех $n \in \mathbb{N}$ имеет место неравенство $0 \leqslant a_n - a_{n+1} \leqslant \frac{2}{n^2}$.

\begin{center}
{\bf Летние сборы 2001. Группа А. Олимпиада \No 5.}
\end{center}

\textbf{1}. Найдите все функции $f: \mathbb{R} \to \mathbb{R}$, удовлетворяющие уравнению $f(x+2^y) = f(2^x) + f(y)$.

\textbf{2}. Дан равнобедренный треугольник $ABC$ ($AB = BC$), угол при вершине $B$ равен $2\beta$.
Через вершину $B$ проведена прямая $\ell$, не персекающая стороны $AC$ треугольника.
Внутри треугольника выбрана точка $K$.
Лучи $AK$ и $CK$ пересекают $\ell$ в точках $P$ и $Q$ соответственно.
Оказалось, что $\angle QAB + \angle PCB = 90^\circ + \beta$.
Чему может равняться угол $\angle AKC$?

\textbf{3}. Какое наибольшее число подмножеств можно выбрать в $n$-элементном множестве так, что любые два из них имеют непустое пересечение, а пересечение любых трех множеств пусто?

\textbf{4}. Пусть $f(x_1, x_2, \dots, x_n)$ --- многочлен с целыми коэффициентами степени строго меньше $n$.
Докажите, что количество упорядоченных наборов $(x_1, x_2, \dots, x_n)$, где $0 \leqslant x_k \leqslant 12$ при $k = 1$, $2$, \dots, $n$, таких что $f(x_1, x_2, \dots, x_n) \vdots 13$ делится на $13$.

\begin{center}
{\bf Летние сборы 2001. Группа Б. Олимпиада \No 5.}
\end{center}

\textbf{1}. Докажите неравенство $\sin x_1 \sin x_2 \dots \sin x_{100} + \cos x_1 \cos x_2 \dots \cos x_{100} \leqslant 1$.

\textbf{2}. Решите уравнение в целых числах: $[n\sqrt{2}] - [m\sqrt{2}] = 2m$.

\textbf{3}. Дан равнобедренный треугольник $ABC$ ($AB = BC$), угол при вершине $B$ равен $2\beta$.
Через вершину $B$ проведена прямая $\ell$, не пересекающая стороны $AC$ треугольника.
Внутри треугольника выбрана точка $K$.
Лучи $AK$ и $CK$ пересекают $\ell$ в точках $P$ и $Q$ соответственно.
Оказалось, что $\angle QAB + \angle PCB = 90^\circ + \beta$.
Чему может равняться угол $\angle AKC$?

\textbf{4}. В графе $n$ вершин и $m$ ребер.
Докажите, что в нем можно выбрать хотя бы $\frac{n^2}{n+2m}$ вершин так, чтобы никакие две из них не были соединены ребром.
%\end{multicols}
\end{document}
